package datastructure.skiplist;

/**
 * 跳跃表 应该是若干个节点数组  数组的每个元素都有自己的next  上层的next跨度大 下层的next跨度小
 *
 *
 * add  search del 的查找都是  for （ 向下移动level） 中 while （向右移动node）  node从head开始双向移动
 *
 *
 *
 *
 */
// 性能差异怎么这么大？  本地测试差异并不大 可能是力扣上有差异
class Skiplist_st {
    /**
     * 最大层数
     */
    private static int DEFAULT_MAX_LEVEL = 32;
    /**
     * 随机层数概率，也就是随机出的层数，在 第1层以上(不包括第一层)的概率，层数不超过maxLevel，层数的起始号为1
     */
    private static double DEFAULT_P_FACTOR = 0.25;

    Node head = new Node(null,DEFAULT_MAX_LEVEL); //头节点

    int currentLevel = 1; //表示当前nodes的实际层数，它从1开始


    public Skiplist_st() {
    }

    public boolean search(int target) {
        Node searchNode = head;
        for (int i = currentLevel-1; i >=0; i--) {
            searchNode = findClosest(searchNode, i, target);
            if (searchNode.next[i]!=null && searchNode.next[i].value == target){
                return true;
            }
        }
        return false;
    }

    /**
     *
     * @param num
     */
    public void add(int num) {
        int level = randomLevel();
        Node updateNode = head;
        Node newNode = new Node(num,level);
        // 计算出当前num 索引的实际层数，从该层开始添加索引
        for (int i = currentLevel-1; i>=0; i--) {
            //找到本层最近离num最近的list
            updateNode = findClosest(updateNode,i,num);
            if (i<level){
                if (updateNode.next[i]==null){
                    updateNode.next[i] = newNode;
                }else{
                    Node temp = updateNode.next[i];
                    updateNode.next[i] = newNode;
                    newNode.next[i] = temp;
                }
            }
        }
        if (level > currentLevel){ //如果随机出来的层数比当前的层数还大，那么超过currentLevel的head 直接指向newNode
            for (int i = currentLevel; i < level; i++) {
                head.next[i] = newNode;
            }
            currentLevel = level;
        }

    }

    public boolean erase(int num) {
        boolean flag = false;
        Node searchNode = head;
        for (int i = currentLevel-1; i >=0; i--) {
            searchNode = findClosest(searchNode, i, num);
            if (searchNode.next[i]!=null && searchNode.next[i].value == num){
                //找到该层中该节点
                searchNode.next[i] = searchNode.next[i].next[i];
                flag = true;
                continue;
            }
        }
        return flag;
    }

    /**
     * 找到level层 value 大于node 的节点
     * @param node
     * @param levelIndex
     * @param value
     * @return
     */
    private Node findClosest(Node node,int levelIndex,int value){
        while ((node.next[levelIndex])!=null && value >node.next[levelIndex].value){
            node = node.next[levelIndex];
        }
        return node;
    }


    /**
     * 随机一个层数
     */
    private static int randomLevel(){
        int level = 1;
        while (Math.random()<DEFAULT_P_FACTOR && level<DEFAULT_MAX_LEVEL){
            level ++ ;
        }
        return level;
    }


    class Node{
        Integer value;
        Node[] next;

        public Node(Integer value,int size) {
            this.value = value;
            this.next = new Node[size];
        }

        @Override
        public String toString() {
            return String.valueOf(value);
        }
    }

}
class Skiplist {
    // maxLevel拿来加速查找用的
    // 也可以直接从32层开始 但是这样效率低了 会有无效循环
    int maxLevel = 0;
    Node  head = new Node(0, 32);

    public Skiplist() {

    }

    public boolean search(int target) {
        Node cur = head;
        for(int i = maxLevel; i >= 0; i--) {
            cur = getMaxLtNodeAtLevel(cur, target, i);
            // cur.next[i] == null 可能是一个高level的节点 该层没有后续 但是  下边节点可能有后续
            if(cur.next[i] != null && cur.next[i].val == target) return true;
        }
        return false;
    }

    /**
     * @param num
     * 从上向下 找每层的目标位置
     */
    public void add(int num) {
        Node node = new Node(num);
        int totalLevel = node.next.length - 1;
        Node preNode = head;
        int val = node.val;
        // 找到每一层小于node的左边的node 并在其后插入
        // Math.min() 保证大于totalLevel的在下边if处理
        // preNode循环使用
        // 是因为越高层离当前节点肯定更远  因此下层节点在高层基础上往后找就行了
        for (int i = Math.min(totalLevel, maxLevel) ; i >= 0; i--) {
            preNode = getMaxLtNodeAtLevel(preNode, val, i);
            node.next[i] = preNode.next[i];
            preNode.next[i] = node;
        }
        // 大于maxLevel的直接连到Head
        if(maxLevel < totalLevel) {
            for (int j = maxLevel + 1; j <= totalLevel; j++) {
                head.next[j] = node;
            }
            maxLevel = totalLevel;
        }

    }

    public boolean erase(int num) {
        Node cur = head;
        boolean finded = false;
        for(int i = maxLevel; i>=0; i--) {
            cur = getMaxLtNodeAtLevel(cur, num, i);
            if(cur.next[i] != null && cur.next[i].val == num) {
                cur.next[i] = cur.next[i].next[i];
                finded = true;
            }
        }
        return finded;
    }

    private Node getMaxLtNodeAtLevel(Node cur, int val, int level) {

        while ( cur.next[level] != null && cur.next[level].val<val) {
            cur = cur.next[level];
        }
        return cur;
    }


}

/**
 * 单个跳表节点每一级指向不同的多个跳表节点
 * 可以看作是链表的变种
 */
class Node {
    int val;
    /**
     * 可以省略  next数组的长度就是level
     */
    // int level;
    Node[] next;

    public Node(int val) {
        this.val = val;
        this.next = new Node[randomLevel()];
    }


    public Node(int val, int level) {
        this.val = val;
        this.next = new Node[level];
    }
    private int randomLevel(){
        int level = 1;
        while(Math.random() < 1 / 4 && level < 32) {
            level ++;
        }
        return level;
    }

    @Override
    public String toString() {
        return String.valueOf(val);
    }

}

public class  设计跳表_1206{
    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        Skiplist skiplist = new Skiplist();
        skiplist.add(1);
        skiplist.add(2);
        skiplist.add(3);
        skiplist.search(0);
        skiplist.add(4);
        skiplist.search(1);
        skiplist.add(5);
        skiplist.search(3);
        skiplist.search(6);
        System.out.println("standard time cost :" + (System.currentTimeMillis() - start));

        long start_st = System.currentTimeMillis();
        Skiplist_st skiplist_st = new Skiplist_st();
        skiplist_st.add(1);
        skiplist_st.add(2);
        skiplist_st.add(3);
        skiplist_st.search(0);
        skiplist_st.add(4);
        skiplist_st.search(1);
        skiplist_st.add(5);
        skiplist_st.search(3);
        skiplist_st.search(6);
        System.out.println("st time cost :" + (System.currentTimeMillis() - start_st));
    }
}




